import "babel-polyfill";
import {map} from "../../algorithm/iterator";
import {MathError} from "../error";
import Integer, {range} from "../number/integer";
import {gcd, invmod} from "../number-theory/gcd";
import PolynomialTemplate from "./polynomial";

const {min} = Math;
const {zero, one, eq, compare, abs, negate, add, subtract, multiply, square, mod, shl, shr} = Integer;

var trim = function() {
    while (this.length && this[this.length - 1].sign === 0) {
        this.pop();
    }
    return this;
};

export default function(modulus) {
    modulus = Integer.from(modulus);
    if (compare(modulus, Integer[2]) < 0) {
        throw new MathError(`modulus(${modulus}) should be integer greater than 1`);
    }
    var half_modulus = shr(modulus, 1);
    if (compare(modulus, 1024) <= 0) {
        let inverse_table = [...range(modulus)::map(n => invmod(n, modulus))];
        var inverse = n => inverse_table[n.lastLimb];
    } else {
        var inverse = n => invmod(n, modulus);
    }

    var IntegerResidue = n => mod(n, modulus);
    Object.assign(IntegerResidue, {
        zero,
        one,
        isZero: n => n.sign === 0,
        isOne: n => eq(n, one),
        eq,
        negate: n => n.sign === 0 ? zero : subtract(modulus, n),
        add: function(m, n) {
            var result = add(m, n);
            return compare(result, modulus) < 0 ? result : subtract(result, modulus);
        },
        subtract: function(m, n) {
            var result = subtract(m, n);
            return result.sign >= 0 ? result : add(result, modulus);
        },
        multiply: (m, n) => mod(multiply(m, n), modulus),
        square: n => mod(square(n), modulus),
        divide: (m, n) => mod(multiply(m, inverse(n)), modulus),
        inverse: n => invmod(n, modulus)
    });

    var PolynomialZn = class extends PolynomialTemplate(IntegerResidue) {
        _fromString(string, symbol = "x") {
            if (!string) {
                throw new MathError("Invalid String");
            } else if (!/^[_A-Za-z][_A-Za-z0-9]*$/.test(symbol)) {
                throw new MathError(`Invalid Symbol ${symbol}`);
            }

            var throw_error = function() {
                throw new MathError(`Invalid String ${string}`);
            };
            var trim = function() {
                while (string[++offset] === " ");
            };
            var op_priority = {
                "+": 0,
                "-": 0,
                "*": 1,
                "^": 2
            };
            var do_operation = function(s) {
                if (stack.length === 1) {
                    if (arguments.length) {
                        stack.unshift(s);
                    }
                } else {
                    if (arguments.length === 0 || op_priority[s] <= op_priority[stack[stack.length - 3]]) {
                        let p2 = stack.pop();
                        let p1 = stack.pop();
                        let op = {
                            "+": this::this.add,
                            "-": this::this.subtract,
                            "*": this::this.multiply
                        }[stack.pop()];
                        stack.push(op(p1, p2));
                        if (arguments.length) {
                            do_operation(s);
                        } else {
                            do_operation();
                        }
                    } else {
                        stack.push(s, stack.pop());
                    }
                }
            }.bind(this);
            var parse_symbol = function() {
                if (string.slice(offset, offset + symbol.length) === symbol) {
                    stack.push(new PolynomialZn(0, 1));
                    offset += symbol.length - 1;
                    trim();
                    status = 2;
                } else {
                    throw_error();
                }
            };

            var stack = [];
            var status = 0;
            var length = string.length;
            var offset = 0;
            if (string[offset] === "+") {
                trim();
            } else if (string[offset] === "-") {
                stack.push("-", PolynomialZn.zero);
                trim();
            }
            while (true) {
                if (status === 0) {
                    if ("0123456789".includes(string[offset])) {
                        let offset2 = offset;
                        while ("0123456789".includes(string[++offset2]));
                        stack.push(new PolynomialZn(new Integer(string.slice(offset, offset2))));
                        offset = offset2 - 1;
                        trim();
                        status = 1;
                    } else {
                        parse_symbol();
                    }
                } else if (status === 1) {
                    if (offset === length) {
                        break;
                    } else if (string[offset] === "+" || string[offset] === "-") {
                        do_operation(string[offset]);
                        trim();
                        status = 3;
                    } else if (string[offset] === "*") {
                        stack.push("*", stack.pop());
                        trim();
                        parse_symbol();
                    } else {
                        throw_error();
                    }
                } else if (status === 2) {
                    if (string[offset] === "^") {
                        trim();
                        if ("0123456789".includes(string[offset])) {
                            let offset2 = offset;
                            while ("0123456789".includes(string[++offset2]));
                            let object = {};
                            object[string.slice(offset, offset2)] = 1;
                            stack[stack.length - 1] = new PolynomialZn().set(object);
                            offset = offset2 - 1;
                            trim();
                            status = 4;
                        } else {
                            throw_error();
                        }
                    } else {
                        status = 4;
                    }
                } else if (status == 3) {
                    if ("0123456789".includes(string[offset])) {
                        let offset2 = offset;
                        while ("0123456789".includes(string[++offset2]));
                        stack.push(new PolynomialZn(new Integer(string.slice(offset, offset2))));
                        offset = offset2 - 1;
                        trim();
                        status = 1;
                    } else {
                        parse_symbol();
                    }
                } else if (status === 4) {
                    if (offset === length) {
                        break;
                    } else if (string[offset] === "+" || string[offset] === "-") {
                        do_operation(string[offset]);
                        trim();
                        status = 3;
                    } else {
                        throw_error();
                    }
                }
            }

            do_operation();
            this._coeff = stack[0]._coeff;
        }

        toString(symbol = "x") {
            var data = this._coeff;
            if (data.length === 0) {
                return "0";
            }
            var list = [];
            if (data[0].sign) {
                let coeff = data[0];
                if (compare(coeff, half_modulus) > 0) {
                    coeff = subtract(coeff, modulus);
                }
                list.push(`${coeff}`);
            }
            for (let degree = 1, length = data.length; degree < length; ++degree) {
                let coeff = data[degree];
                if (coeff.sign) {
                    if (compare(coeff, half_modulus) > 0) {
                        coeff = subtract(coeff, modulus);
                    }
                    if (eq(abs(coeff), one)) {
                        if (list.length === 0) {
                            if (coeff.sign < 0) {
                                list.push("-");
                            }
                        } else {
                            list.push(coeff.sign > 0 ? " + " : " - ");
                        }
                    } else {
                        if (list.length === 0) {
                            list.push(`${coeff}*`);
                        } else {
                            list.push(coeff.sign > 0 ? " + " : " - ", `${abs(coeff)}*`);
                        }
                    }
                    list.push(degree === 1 ? symbol : `${symbol}^${degree}`);
                }
            }
            return list.join("");
        }

        square(p) {
            var data = this.from(p)._coeff;
            var length = data.length;
            if (length === 0) {
                return PolynomialZn.zero;
            }
            var result = [mod(square(data[0]), modulus)];
            for (let i = 1; i < length; ++i) {
                result.push(zero, mod(square(data[i]), modulus));
                for (let j = 0; j < i; ++j) {
                    result[i + j] = mod(add(result[i + j], shl(multiply(data[i], data[j]), 1)), modulus);
                }
            }
            return this._create(result::trim());
        }
    };

    PolynomialZn.zero = new PolynomialZn();
    PolynomialZn.one = new PolynomialZn(1);
    PolynomialZn.instance = new PolynomialZn();
    PolynomialZn.modulus = modulus;

    return PolynomialZn;
};

export var SquarePolynomialZn = function(PolynomialType) {
    var modulus = square(PolynomialType.modulus);
    var half_modulus = shr(modulus, 1);
    if (compare(modulus, 1024) <= 0) {
        let inverse_table = [...range(modulus)::map(n => invmod(n, modulus))];
        var inverse = n => inverse_table[n.lastLimb];
    } else {
        var inverse = n => invmod(n, modulus);
    }

    var IntegerResidue = n => mod(n, modulus);
    Object.assign(IntegerResidue, {
        zero,
        one,
        isZero: n => n.sign === 0,
        isOne: n => eq(n, one),
        eq,
        negate: n => n.sign === 0 ? zero : subtract(modulus, n),
        add: function(m, n) {
            var result = add(m, n);
            return compare(result, modulus) < 0 ? result : subtract(result, modulus);
        },
        subtract: function(m, n) {
            var result = subtract(m, n);
            return result.sign >= 0 ? result : add(result, modulus);
        },
        multiply: (m, n) => mod(multiply(m, n), modulus),
        square: n => mod(square(n), modulus),
        divide: (m, n) => mod(multiply(m, inverse(n)), modulus),
        inverse: n => invmod(n, modulus)
    });

    var PolynomialZn = class extends PolynomialTemplate(IntegerResidue) {
        from(p) {
            return this._create(p._coeff);
        }

        truncMultiply(p1, p2, degree) {
            var data1 = p1._coeff;
            var data2 = p2._coeff;
            if (data1.length === 0 || data2.length === 0) {
                return this.constructor.zero;
            }
            if (data1.length > data2.length) {
                [data1, data2] = [data2, data1];
            }
            var l1 = data1.length;
            var l2 = data2.length;
            var result = new Array(degree).fill(zero);
            for (let i = 0, L1 = min(l1, degree); i < L1; ++i) {
                for (let j = 0, L2 = min(l2, degree - i); j < L2; ++j) {
                    result[i + j] = mod(add(result[i + j], multiply(data1[i], data2[j])), modulus);
                }
            }
            return this._create(result::trim());
        };
    };

    PolynomialZn.zero = new PolynomialZn();
    PolynomialZn.one = new PolynomialZn(1);
    PolynomialZn.instance = new PolynomialZn();
    PolynomialZn.modulus = modulus;

    return PolynomialZn;
}
